746. 使用最小花费爬楼梯

Similar Question

Solution Tips

方案一: 递归方案

特别像二叉树的子树递归, 其实这个递归的流程也可以抽象画成一颗二叉树, 因为对于每一个台阶, 都有两个选择可以跳到这个台阶

var minCostClimbingStairs = function(cost) {
    // 感觉总体还是和 fibo 很像的
    return dfs(cost, cost.length)

    function dfs(cost, i) {
        if (i === 0) {
            return cost[0];
        }
        if (i === 1) {
            return Math.min(cost[0], cost[1]);
        }

        const prev = dfs(cost, i - 1)
        const prevPrev = dfs(cost, i - 2);
        return (cost[i] || 0) + Math.min(prev, prevPrev);
    }
};

方案二: 经典 DP

var minCostClimbingStairs = function(cost) {
    const n = cost.length
    // 1. dp[i] 代表从第 i 个台阶出发, 到达顶点的 cost
    // 3. dp[n] = 0 已经在顶点了, 花费 0
    // dp[n - 1] = cost[n - 1]
    // dp[n - 2] = cost[n - 2]
    // dp[n - 3] = cost[n - 3] + Math.min(dp[n-1], dp[n-2])
    // 2. dp[i] = cost[i] + Math.min(dp[i+1], dp[i+2])
    // 4. 从后到前初始化
    if (cost.length <= 2) {
        return Math.min(cost[0], cost[1]);
    }

    const dp = [];
    dp[n] = 0;
    dp[n - 1] = cost[n - 1];
    dp[n - 2] = cost[n - 2];
    let i = n - 3;
    while (i >= 0) {
        dp[i] = cost[i] + Math.min(dp[i + 1], dp[i + 2]);
        i--;
    }

    return Math.min(dp[0], dp[1]);
};

console.log(minCostClimbingStairs([1,100,1,1,1,100,1,1,100,1]))

同样可以用滚动数组做一下优化, 这种题目, 感觉都是斐波那契的变种

方案三: 贪心 + 从前遍历? + DP

代码随想录

如果每次都选择最小的那个, 最终会是最小的吗?

var minCostClimbingStairs = function(cost) {
    const n = cost.length;
    let prev = 0, curr = 0;
    for (let i = 2; i <= n; i++) {
        let next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
        prev = curr;
        curr = next;
    }
    return curr;
};